class Solution(object):
    def magicalString(self, n):
        """
        :type n: int
        :rtype: int
        """
        s = [0] * n
        left = 0
        right = 0
        s[0] = 1
        while right + 1 < n:
            s[right + 1] = 3 - s[right]
            right += 1
            left += 1
            if s[left] == 2:
                if right + 1 < n:
                    s[right + 1] = s[right]
                    right += 1
        print(s)
        return s.count(1)

data = Solution()
n = 15
print(data.magicalString(n))